package collectionTest;

public class HeapTest {
    public static void main(String[] args) {

    }
    // 告诉我这个数组的有效长度,有效长度需要用户记住
    // 本来可以做为一个用户属性
    public static int pop(int[] arr,int n){
        int temp =arr[0];
        arr[0] = arr[n-1];
        siftDown(arr,n-1);
        return  temp;
    }

    // n是队列的有效索引,ele,最后一个
    public static void  push(int[] arr,int n){
        siftUp(arr,n);
    }

    // 摘取元素后,arr[1]是不对的,n是有效索引
    public static  void siftDown(int[] arr,int n){
        int i = 1;
        while (2*i<=n){
            // 2*i,2*i+1
            // 如何简化代码？
            if(2*i==n){
                if(arr[i]>arr[2*i]){
                    swap(arr,i,2*i);
                }
                break;
            }
            if (arr[i] <=arr[2*i] && arr[i] < arr[2*i+1]){
                break;
            }else if(arr[2*i] < arr[2*i+1]){
                    swap(arr,i,2*i);
                }else {
                    swap(arr,i,2*i+1);
            }
        }
    }

    // 增加元素后
    public static void siftUp(int[] arr,int n){
       while (n>1 && arr[n/2]>arr[n]){
           n = n/2;
           int temp =arr[n];
           arr[n] = arr[n/2];
           arr[n/2] = temp;
       }
       return;
    }

    public static void swap(int[] arr,int i,int j){
        int temp = arr[i];
        arr[i] = arr[j];
        arr[j] =temp;
    }
}
